package myTest;
import java.io.*;
import java.util.*;

public class findPath{
	static String busMapFile="C:\\Users\\ChengXin\\Desktop\\busMap.txt";
	static String busANDstationFile="C:\\Users\\ChengXin\\Desktop\\busANDstation.txt";
	
	static String[] bus, station;
	
	public static int SameBus(int src, int dst, int[][] busMap){
		for(int i=0; i<busMap.length; i++)
			if(busMap[i][src]!=0 && busMap[i][dst]!=0)
				return i;
		return -1;
	}
	
	public static int[][] getBusMap(){
		int [][] busMap=new int[328][2582];
		try{
			String s;
			BufferedReader in=new BufferedReader(new FileReader(busMapFile));
			int row=0;
			while((s=in.readLine())!=null){
				String array[]=s.split(" ");
				for(int i=0; i<array.length; i++)
					busMap[row][i]=Integer.valueOf(array[i]).intValue();
				row++;
			}
		}
		catch(Exception e){
			System.out.println(e.toString());
		}
		return busMap;
	}
	
	public static void main(String[] args){
		try{
			String s;
			BufferedReader in=new BufferedReader(new FileReader(busMapFile));
			/*
			int row=0;
			while((s=in.readLine())!=null){
				String array[]=s.split(" ");
				for(int i=0; i<array.length; i++)
					busMap[row][i]=Integer.valueOf(array[i]).intValue();
				row++;
			}
			*/
			in=new BufferedReader(new FileReader(busANDstationFile));
			s=in.readLine();
			s=in.readLine();
			bus=s.split(" ");
			s=in.readLine();
			station=s.split(" ");
		}
		catch(Exception e){
			System.out.println(e.toString());
		}
		
		int[][] busMap=getBusMap();

		String result="";
		int src=80;
		int dst=100;
		/*
		Queue<Integer> queue=new LinkedList<Integer>();
		int currentSrc, samebus;
		queue.offer(src);
		
		while(!queue.isEmpty()){
			currentSrc=queue.poll();
			samebus=SameBus(currentSrc,dst,busMap);
			if(samebus>-1){
				result += station[currentSrc]+"("+currentSrc+")"+"\n{"+bus[samebus]+"}\n"+station[dst]+"("+dst+")";
				break;
			}
			else
				for(int i=1; i<bus.length; i++)
					if(busMap[i][currentSrc]>0){
						queue.offer(busMap[i][currentSrc]);
						busMap[i][currentSrc]=0;
					}
				
		}
		
		result += "\n";
		
		src=806;
		dst=35;
		queue.offer(src);
		
		while(!queue.isEmpty()){
			currentSrc=queue.poll();
			samebus=SameBus(currentSrc,dst,busMap);
			if(samebus>-1){
				result += station[currentSrc]+"("+currentSrc+")"+"\n{"+bus[samebus]+"}\n"+station[dst]+"("+dst+")";
				break;
			}
			else
				for(int i=1; i<bus.length; i++)
					if(busMap[i][currentSrc]>0){
						queue.offer(busMap[i][currentSrc]);
						busMap[i][currentSrc]=0;
					}
				
		}
		*/
		result=leastBus(src,dst,busMap);
		System.out.print(result+station[dst]+"("+dst+")");
		//System.out.print(result);
	}
	
	public static String leastBus(int src, int dst, int[][] busMap){
		if(SameBus(src,dst,busMap)>-1)
			return station[src]+"("+src+")"+"\n{"+bus[SameBus(src,dst,busMap)]+"}\n";
		else{
			Queue<Integer> queue=new LinkedList<Integer>();
			int currentSrc, samebus;
			queue.offer(src);
			
			while(!queue.isEmpty()){
				currentSrc=queue.poll();
				samebus=SameBus(currentSrc,dst,busMap);
				if(samebus>-1){
					busMap=getBusMap();
					return leastBus(src,currentSrc,busMap)+station[currentSrc]+"("+currentSrc+")"+"\n{"+bus[samebus]+"}\n";
				}
				else
					for(int i=1; i<bus.length; i++)
						if(busMap[i][currentSrc]>0){
							queue.offer(busMap[i][currentSrc]);
							busMap[i][currentSrc]=0;
						}
					
			}
		}
		return "No Path!";
	}
}